'''
https://leetcode.cn/problems/remove-invalid-parentheses/
'''
from typing import List


class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        n = len(s)
        l, r = 0, 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                r += 1
        maxl = min(l, r)
        res = set()
        path = []
        max_len = 0

        def f(i, left):
            nonlocal max_len, res
            if left < 0 or left > maxl:
                return
            if i == n:
                if left == 0:
                    if len(path) > max_len:
                        max_len = len(path)
                        res = {''.join(path)}
                    elif len(path) == max_len:
                        res.add(''.join(path))
                return
            if s[i] == '(':
                f(i + 1, left)
                path.append(s[i])
                f(i+1, left+1)
                path.pop()
            elif s[i] == ')':
                f(i + 1, left)
                path.append(s[i])
                f(i+1, left-1)
                path.pop()
            else:
                path.append(s[i])
                f(i+1, left)
                path.pop()

        f(0, 0)
        return list(res)

s = "(((((((((((((((aaaa)))))"
print(Solution().removeInvalidParentheses(s))